package com.zyk.leetcode;

/**
 *
 * https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/
 *
 * @author zhangsan
 * @date 2021/4/3 14:43
 */
public class J55 {



    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static int maxDepth(TreeNode root) {
        return process(root);
    }

    private static int process(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = process(root.left);
        int right = process(root.right);
        return Math.max(left, right) + 1;
    }

    public static class IsBalancedInfo {
        int height;
        boolean isBalanced;

        public IsBalancedInfo(int height, boolean isBalanced) {
            this.height = height;
            this.isBalanced = isBalanced;
        }
    }

    /** https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/ */
    public static boolean isBalanced(TreeNode root) {
        return process2(root).isBalanced;
    }

    private static IsBalancedInfo process2(TreeNode root) {
        if(root == null) {
            return new IsBalancedInfo(0, true);
        }
        IsBalancedInfo lInfo = process2(root.left);
        IsBalancedInfo rInfo = process2(root.right);
        int height = Math.max(lInfo.height, rInfo.height) + 1;
        boolean isBalanced = true;
        if(!lInfo.isBalanced || !rInfo.isBalanced || (Math.abs(lInfo.height - rInfo.height) > 1)) {
            isBalanced = false;
        }
        return new IsBalancedInfo(height, isBalanced);
    }

}
